%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% input
\KwIn{A directed or undirected graph $G = (V, E)$ of order $n > 0$. A
  vertex $s$ from which to start the search. The vertices are numbered
  from $1$ to  $n = |V|$, i.e.~$V = \{1, 2, \dots, n\}$.}
%%
%% output
\KwOut{A list $D$ of distances of all vertices from $s$. A tree $T$
  rooted at $s$.}
\BlankLine
%%
%% algorithm body
$S \assign [s]$\tcc*[f]{stack of nodes to visit}\;
$D \assign [\infty, \infty, \dots, \infty]$\tcc*[f]{$n$ copies of $\infty$}\;
$D[s] \assign 0$\;
$T \assign [\,]$\;
\While{$\length(S) > 0$\nllabel{alg:DFS:while_loop_tests_non_empty_stack}}{
  $v \assign \pop(S)$\;
  \For{\rm each $w \in \adj(v)$\nllabel{alg:DFS:for_loop_visit_neighbors}}{
    \If{$D[w] = \infty$\nllabel{alg:DFS:if_test_unvisited_neighbors}}{
      $D[w] \assign D[v] + 1$\;
      $\push(S, w)$\;
      $\append(T, vw)$\;
    }
  }
}
\Return $(D, T)$\;
